//
// Created by Administrator on 2021/8/11.
//
//给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
//
//请你设计并实现时间复杂度为O(n) 的算法解决此问题。
//

#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <string>
#include <climits>

using namespace std;

class Solution {
public:
    int longestConsecutive(vector<int> &nums) {
        unordered_set<int> num_set;
        // set 去重
        for (const int &num : nums) {
            num_set.insert(num);
        }
        int longestStreak = 0;
        for (const int &num : num_set) {
            // 应该从最左端开始
            if (!num_set.count(num - 1)) {
                int currentNum = num;
                int currentStreak = 1;
                // 找从num开始的最长序列
                while (num_set.count(currentNum + 1)) {
                    currentNum += 1;
                    currentStreak += 1;
                }
                longestStreak = max(longestStreak, currentStreak);
            }
        }
        return longestStreak;
    }
};


int main() {
    vector<int> nums{0, 3, 7, 2, 5, 8, 4, 6, 0, 1};
    Solution solution;
    cout << solution.longestConsecutive(nums) << endl;
    return 0;
}
